package 力扣_简单题;


import java.util.Arrays;

/**
 * @author 连安利
 * @version 1.0
 * @date 2021/3/30 14:20
 */
public class 合并两个有序数组 {
//    方法一：暴力合并后排序
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
    }
//    方法二：双指针 ，从前往后，空间复杂度O（m），时间复杂度O(m+n)
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int nums3[] = Arrays.copyOf(nums1,m);
        int p1 = 0, p2 = 0, p = 0;
        while(p1 < m && p2 <n){
            if(nums3[p1] > nums2[p2]){
                nums1[p] = nums2[p2];
                p++;
                p2++;
            }
            else
            {
                nums1[p] = nums3[p1];
                p++;
                p1++;
            }
        }
        if(p1 < m){
            System.arraycopy(nums3, p1, nums1, p,m-p1);
        }
        if(p2 < n){
            System.arraycopy(nums2, p2, nums1, p, n-p2);
        }
    }
    //    方法三：双指针 ，从后往前,空间复杂度O（1）, 时间复杂度O (m+n)
    public void merge3(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m-1;
        int p2 = n-1;
        int p = n+m-1;
        while(p1 >= 0 && p2 >= 0){
            if(nums1[p1] > nums2[p2]){
                nums1[p] = nums1[p1];
                p--;
                p1--;
            }
            else {
                nums1[p] = nums2[p2];
                p--;
                p2--;
            }
        }
//        如果此时p1未走完，p2已走完，那么就是结果，不用再计算
//        如果此时p1已走完，但是p2未走完，那么就需要将剩下的nums2中的元素复制进去；
//        还有一种情况就是nums1为空，那么就不执行循环，那么p2就等于0，所以这里不用进行判断p2是否不等于0
            System.arraycopy(nums2,0, nums1, 0, p2+1);
    }
}
